package com.spirng.leetcode.day01;

import java.util.ArrayList;

public class Array2_2 {
    public static void main(String[] args) {
//        searchRange(new int[]{3,5,5,6},5);
        Array2_2 array22 = new Array2_2();
        array22.backspaceCompare("a#c","b");
        ArrayList<Object> list = new ArrayList<>();
        list.add(1);
    }
    public static int[] searchRange(int[] nums, int target) {
        int left=0;
        int right=nums.length-1;
        int leftBorder = findLeftBorder(left, right, nums, target);
        int rightBorder = findRightBorder(left, right, nums, target);
        if (leftBorder==-2||rightBorder==-2){
            return new int[]{-1,-1};
        }
        if(rightBorder-leftBorder>1){
            return new int[]{leftBorder+1,rightBorder-1};
        }
        return new int[]{-1,-1};
    }
    //先确定右边界
    public static int findRightBorder(int left,int right,int []nums,int target){
        int rightBorder=-2;
        while(left<=right){
            int middle=(left+right)/2;
            if(nums[middle]>target){
                right=middle-1;
            }else {
                left=middle+1;
                rightBorder=left;
            }
        }
        return rightBorder;
    }
    //确定左边界
    public static int findLeftBorder(int left,int right,int []nums,int target){
        int leftBorder=-2;
        while(left<=right){
            int middle=(left+right)/2;
            if(nums[middle]>=target){
                right=middle-1;
                leftBorder=right;
            }else
            {
                left=middle+1;
            }
        }
        return leftBorder;
    }
    public  int testxx(int [] nums,int target){
        int left=0;
        int right=nums.length-1;
        while (left<=right){
            int middle=(left+right)/2;
            if(nums[middle]<target){
                left=middle+1;
            } else if (nums[middle]>target) {
                right=middle-1;
            }else {
                return middle;
            }
        }
        return -1;
    }
    public int testx(int []nums,int val){
        int slow=0;
        for(int fast=0;fast<nums.length-1;fast++){
            if (nums[fast]!=val) {
                nums[slow]=nums[fast];
                slow++;
            }
        }
        return slow;
    }
    public int searchInsert(int[] nums, int target) {
        int left=0;
        int right=nums.length-1;
        while(left<=right){
            int middle=(left+right)/2;
            if(nums[middle]>target){
                right=middle-1;
            }else if(nums[middle]<target){
                left=middle+1;
            }else{
                return middle;
            }
        }
        return left;
//        int n = nums.length;
//        int left = 0;
//        int right = n - 1; // 定义target在左闭右闭的区间里，[left, right]
//        while (left <= right) { // 当left==right，区间[left, right]依然有效
//            int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
//            if (nums[middle] > target) {
//                right = middle - 1; // target 在左区间，所以[left, middle - 1]
//            } else if (nums[middle] < target) {
//                left = middle + 1; // target 在右区间，所以[middle + 1, right]
//            } else { // nums[middle] == target
//                return middle;
//            }
//        }
//        // 分别处理如下四种情况
//        // 目标值在数组所有元素之前  [0, -1]
//        // 目标值等于数组中某一个元素  return middle;
//        // 目标值插入数组中的位置 [left, right]，return  right + 1
//        // 目标值在数组所有元素之后的情况 [left, right]， 因为是右闭区间，所以 return right + 1
//        return right + 1;
    }
    public int mySqrt(int x) {
        int l=0;
        int r=x;
        int leftBorder=0;
        while (l<=x){
            int middle=(l+r)/2;
            if((long)middle*middle>=x){
                r=middle-1;
                leftBorder=r;
            }else{
                l=middle+1;
            }
        }
        return leftBorder;
    }
    public void moveZeroes(int[] nums) {
        int slow=0;
        for (int fast = 0; fast < nums.length; fast++) {
            if(nums[fast]!=0) {
                nums[slow]=nums[fast];
                slow++;
            }
        }
        while (slow<nums.length){
            nums[slow]=0;
            slow++;
        }
    }
    public static boolean backspaceCompare(String s, String t) {
        char[] sCharArray = s.toCharArray();
        char[] tCharArray = t.toCharArray();
        int skipS=0;
        int skipT=0;
        int i=sCharArray.length-1;
        int j=tCharArray.length-1;
        while (j>=0&&i>=0) {
            while (i >= 0) {
                char c = sCharArray[i];
                if (c == '#') {
                    skipS++;
                    i--;
                } else if (skipS > 0) {
                    skipS--;
                    i--;
                } else {
                    break;
                }
            }
            while (j >=0) {
                char c = tCharArray[j];
                if (c == '#') {
                    skipT++;
                    j--;
                } else if (skipT > 0) {
                    skipT--;
                    j--;
                } else {
                    break;
                }
            }
            if(i<0&&j<0){
                return true;
            }
            if (i>=0&&j>=0&&sCharArray[i] == tCharArray[j]) {
                i--;
                j--;
            }else{
                return false;
            }
        }
        return true;
    }

}
